1. Field of the Invention
The present invention is directed to an asynchronous circuit with completion detection, and a system and method for designing the same. More specifically, the present invention is directed to conversion of a Boolean logic circuit to an asynchronous circuit, optimizing the completeness detection aspects of the circuit, and a system and method for designing the same.
2. Discussion of Background Information
Asynchronous circuits have been proposed that are intended to operate without a clock. One asynchronous logic paradigm is disclosed in U.S. Pat. No. 5,305,463 (xe2x80x9cthe ""463 logic systemxe2x80x9d), issued Apr. 19, 1994, which is incorporated herein by reference in its entirety. Several data representations are discussed, but in one representation a signal may assume a DATA value or a NULL value. A DATA value, for example, might be a numeric value ZERO or ONE, or a logic value TRUE or FALSE, or another meaning not related to binary or Boolean logic representations.
In such a representation, a signal may take the form of two signal lines, with a first signal line designated to mean ZERO or FALSE, and the second signal line designated to mean ONE or TRUE. Each line may assume one of two states: xe2x80x9cASSERTEDxe2x80x9d or xe2x80x9cNULL.xe2x80x9d The meaning of the pair of signal lines is determined by the states of the lines. The pair of lines together represents a single binary variable (such as a single bit of binary data) and have four possible states: (1) ASSERTED, ASSERTED, (2) ASSERTED, NULL, (3) NULL, ASSERTED, and (4) NULL, NULL.
The first state (ASSERTED/ASSERTED) is not permitted. The second state (NULL/ASSERTED) represents/signifies meaningful data of a value ZERO or FALSE. The third state (ASSERTED/NULL) represents/signifies meaningful data of value ONE or TRUE. The fourth state (NULL/NULL) can be thought of as indicating that the variable is in a NULL state and has not assumed a meaningful value.
This representation is known as a multi-rail representation of mutually exclusive assertion groups for asynchronous circuits. Dual-rail representation (i.e., two signal lines with three states: NULL, DATA ZERO and DATA ONE) is a specific subset of multi-rail representation. As used herein, DATA collectively refers to DATA ZERO and DATA ONE states for a dual rail representation (and for any other DATA X states for multi-rail lines with three or more signal lines).
Asynchronous circuits designed consistent with the above require some type of indication that the computations are completed. A circuit is xe2x80x9cindicatingxe2x80x9d if each signal transition xe2x80x9caxe2x80x9d, on an input or internal signal in the circuit, is a cause of a transition xe2x80x9cbxe2x80x9d, on an output signal, that could not occur without xe2x80x9caxe2x80x9d. If an asynchronous circuit is not xe2x80x9cindicating,xe2x80x9d then additional circuitry may be necessary to ensure correct asynchronous operation. Delay Insensitive Minterm Synthesis (DIMS) is a method that uses C-elements as the basis of such additional xe2x80x9ccompletenessxe2x80x9d circuitry. A drawback of DIMS is that it requires a great deal of space and logic elements, with a correspondingly high cost. Further, since the functional aspects of the underlying circuit and the completion aspects are intertwined, it is difficult to reduce or optimize the completion aspects of the circuit without adversely affecting the functionality of the circuit.
At present, while the overwhelming majority of circuit designers can design circuits using Boolean logic, only a small number of designers exist who can design asynchronous circuits that operate using multi-rail signals. While there are certain available methodologies for converting a Boolean expression into an asynchronous circuit (such as DIMS), these methodologies result in large circuits with correspondingly high design and production costs.
The present invention addresses the drawbacks of the prior art.
According to an embodiment of the invention, a design methodology is provided for converting a Boolean logic circuit into an asynchronous circuit.
According to another embodiment of the invention, a design methodology is provided for adding and optimizing completeness detection in an asynchronous circuit.
According to an embodiment of the invention, a method for designing a multi-rail asynchronous circuit is provided. The method includes providing a circuit having n circuit paths, defining a plurality of nodes, each node having an n-rail signal output and at least one n-rail signal input, each rail of the n-rail signal input being connected to a different one of the plurality of circuit paths, and adding completeness detection to each of the plurality of nodes, completion detection for a downstream one of the plurality of nodes being at least partially based on completion detection from an upstream one of the plurality of nodes. Signals propagate along the plurality of data paths independent of the completeness detection.
According to another embodiment of the invention, a method is provided for designing a multi-rail asynchronous circuit that operates using n-rail signals, the circuit including at least one primary input, at least one primary output, and at least one intermediate output. The method includes providing a circuit having n circuit paths, defining a plurality of nodes, each node having at least one n-rail signal output and at least one n-rail signal input, each of the n circuit paths providing a rail of the n-rail signal input, adding completeness detection to at least those nodes that generate intermediate outputs, completion detection for a downstream one of the plurality of nodes being at least partially based on completion detection from an upstream one of the plurality of nodes; and optimizing the completeness detection. The circuit is capable of propagating signals along the plurality of circuit paths independent of the completeness detection.
According to yet another embodiment of the invention, a method is provided for designing a dual-rail asynchronous circuit from a Boolean expression. The method includes converting the Boolean expression into a corresponding first plurality of circuits along a first data path, converting each of the plurality of circuits into an unate circuit, providing a dual circuit along a second data path, each of the dual circuits being the dual of a corresponding unate circuit, each of the unate circuits and the corresponding one of the dual circuits defining a node, and adding completeness detection circuitry for at least each intermediate output between the nodes such that completion detection of at least one downstream node is based at least partially on completion detection of at least one upstream node. The completeness detection circuitry does not affect propagation of signals through the nodes.
According to still another embodiment of the invention, a method is provided for adding completeness to an n-rail asynchronous circuit including a plurality of nodes. The method includes assigning to a completion tree at least all primary inputs to the plurality of nodes and intermediate outputs between any of the plurality of nodes, optimizing the completion tree, comprising at least one of removing duplicate completion detection of any signal, testing whether the plurality of nodes is indicating for any primary input, testing whether the plurality of nodes is indicating for any intermediate output, removing completion detection circuitry that proves unnecessary in response to a result of the optimizing, and designing the circuit based on a result of the removing.
According to still yet another embodiment of the invention, a method is provided for adding completion to an n-rail circuit including a plurality of nodes, each node including n rail circuits that define an n-rail output, the n-rail circuit having k primary inputs. The method includes, for each node, providing circuit logic that can obtain a completion signal for each input to the node, providing circuit logic that can issue a data signal representing the presence of DATA on the n rails of the n-rail output, and inputting the output of the circuit logic for the data signal and completion signal for each input to the node into a completion detector, testing, for each of the k inputs, whether the n-rail circuit is indicating; and removing completion detection for any of the k inputs for which the n-rail circuit is indicating.
According to still yet another embodiment of the invention, an n-rail asynchronous circuit is provided. The circuit includes a plurality of primary inputs to the circuit, a plurality of nodes in a data path, each node representing at least one n-rail circuit, an output from an upstream node to a downstream node representing an intermediate output, and a completion detection circuit capable of receiving completion detection signals for each of the primary inputs to the circuit and each of the intermediate outputs for which the circuit is not inherently indicating.
According to an embodiment of the invention, a register for use in asynchronous n-rail circuits, is provided. The register includes an input side configured to receive at least one n-rail signal and at least one completion signal, an output side configured to output the at least one n-rail signal, a plurality of gates configured to provide a circuit path from the input side to the output side in response to receipt of an external signal, a first completion detector circuit configured to receive each of the at least one completion signal, for each of the at least one n-rail signal, an individual completion detection circuit configured to receive the n-rails of the at least one signal and to output a completion signal, and a second completion detection circuit configured to receive the output of the first completion detection circuit, each of the individual completion circuits. The second completion circuit is configured to provide a completion signal for each of the at least one rail signal on the output side.
Other exemplary embodiments and advantages of the present invention may be ascertained by reviewing the present disclosure and the accompanying drawings.